原题链接895. 最长上升子序列
题目难度：简单
题目描述给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式输出一个整数，表示最大长度。
数据范围$1 \le N \le 1000$，$-10^9 \le 数列中的数 \le 10^9$
输入样例：1273 1 2 1 8 5 6
输出样例：14
题目分析这道题目的意思很简单，就是从序列中找到一个最长的严格递增的子序列，例如样例中的结果就是，1,2,5,6
这是一个经典的DP问题，我们依旧从集合的角度来看，集合的含义就是所有以a[i]结尾的严格单调上升的子序列
从状态计算的角度来看，我们以倒数第二个位置可以取的不同的数字进行集合划分，一共有i种情况，分别是空，a[1]，a[2]一直到a[i-1]，那么对于其中任意一种情况，都可以继续进行划分，当不符合条件的时候，只需要进行排除即可
示例代码12345678910111213141516171819202122232425262728#include<iostream&...
原题链接2. 01背包问题
题目难度：简单
题目描述有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 iii 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 iii 件物品的体积和价值。
输出格式输出一个整数，表示最大价值。
数据范围$0 \lt N, V \le 1000$$0\lt v_i, w_i \le 1000$
输入样例123454 51 22 43 44 5
输出样例：18
题目分析这道题是非常典型的题目，有一类问题都叫背包问题，而这道题目则是最经典的01背包问题，题目的意思也很好理解，最终就是要让背包中的价值最大
这里的01的意思就是，每个物品最多只能使用1次
这里需要用到一个非常重要的分析解决问题的方法叫做动态规划（DP），而这种问题我们也称之为动态规划问题
对于动态规划来说，我们一般从两个方面来...
原题链接1211. 蚂蚁感冒
题目难度：简单
题目来源：第五届蓝桥杯省赛C++ A/B组
题目描述长 100 厘米的细长直杆子上有 n 只蚂蚁。
它们的头有的朝左，有的朝右。
每只蚂蚁都只能沿着杆子向前爬，速度是 1 厘米/秒。
当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。
这些蚂蚁中，有 1 只蚂蚁感冒了。
并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。
请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
输入格式第一行输入一个整数 n, 表示蚂蚁的总数。
接着的一行是 n 个用空格分开的整数 $X_i$, $X_i$ 的绝对值表示蚂蚁离开杆子左边端点的距离。
正值表示头朝右，负值表示头朝左，数据中不会出现 0 值，也不会出现两只蚂蚁占用同一位置。
其中，第一个数据代表的蚂蚁感冒了。
输出格式输出1个整数，表示最后感冒蚂蚁的数目。
数据范围$1<n<50$,$0 < |X_i| < 100$
输入样例1：1235 -2 8
输出样例1：11
输入样例2：125-10 8 -20 12 25
输出样例2：1...
原题链接1216. 饮料换购
题目难度：简单
题目来源：第六届蓝桥杯省赛C++ A/C组,第六届蓝桥杯省赛Java B组
题目描述乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料，凭3个瓶盖可以再换一瓶C型饮料，并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。
输入格式输入一个整数 n,表示初始买入的饮料数量。
输出格式输出一个整数，表示一共能够喝到的饮料数量。
数据范围0 < n < 10000
输入样例：1100
输出样例：1149
题目分析这道题其实就是一种小学数学题目，三个瓶盖换一个饮料，问最多可以喝多少瓶饮料
这种简单的题目就是模拟他兑换的过程
假设我们一开始有n瓶，那么结果就先有n，然后又有了n个瓶盖，那么当n大于等于3的时候就可以一直换，换的瓶数除3下取整，盖子数量就是n除3下取整再加上n除3的余数
示例代码123456789101112131415#include<iostream>using namespa...
原题链接1205. 买不到的数目
题目难度：简单
题目来源：第四届蓝桥杯省赛C++ A组,第四届蓝桥杯省赛Java C组
题目描述小明开了一家糖果店。
他别出心裁：把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式两个正整数 n,m，表示每种包装中糖的颗数。
输出格式一个正整数，表示最大不能买到的糖数。
数据范围2≤n,m≤1000，保证数据一定有解。
输入样例：14 7
输出样例：117
题目分析这道题其实就是非常经典的一道数学题目，题目意思也很简单，就是给两个数，问最大的不能凑出来的数是多少
假设我们不知道这个数学定理，如何尽力去分析呢，首先假设这两个数字是p和q，他们的最大公因数是d，那么对于大于p和q，且因数中没有d的数字是一定凑不出来的，反过来，那么只要他们的最大公因数...
原题链接730. 机器人跳跃问题
题目难度：中等
题目来源：笔试题
题目描述机器人正在玩一个古老的基于 DOS 的游戏。
游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。
编号为 0 的建筑高度为 0 个单位，编号为 iii 的建筑高度为 $H(i)$ 个单位。
起初，机器人在编号为 0 的建筑处。
每一步，它跳到下一个（右边）建筑。
假设机器人在第 k 个建筑，且它现在的能量值是 EEE，下一步它将跳到第 $k+1$ 个建筑。
如果 $H(k+1)>E$，那么机器人就失去 $H(k+1)-E$ 的能量值，否则它将得到 $E-H(k+1)$ 的能量值。
游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
输入格式第一行输入整数 N。
第二行是 N 个空格分隔的整数，$H(1),H(2),…,H(N)$ 代表建筑物的高度。
输出格式输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。
数据范围$1 \le N,H(i) \le 10^5,$
输入样例1：1253 4 ...
原题链接1230. K倍区间
题目难度：中等
题目来源：第八届蓝桥杯省赛C++ B组,第八届蓝桥杯省赛Java B/C组
题目描述给定一个长度为 NNN 的数列，$A_1, A_2, … A_N$，如果其中一段连续的子序列 $A_i, A_{i+1}, … A_j$ 之和是 K 的倍数，我们就称这个区间 $[i, j]$ 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式第一行包含两个整数 N 和 K。
以下 NNN 行每行包含一个整数 $A_i$。
输出格式输出一个整数，代表 K 倍区间的数目。
数据范围$1 \le N, K \le 100000$,$1 \le A_i \le 100000$
输入样例：1234565 212345
输出样例：16
题目分析题目意思十分清楚，就是给一个静态数组，问其中有多少个连续子数组的和是K的倍数
这里我们观察数据范围，大概采用的时间复杂度要小于$O(n\log n)$
我们如果用最暴力的做法，枚举所有方案，对于枚举来说最重要的就是如何能够不重不漏的枚举出所有方案
对于这个题而言，就是枚举左端点和右端点...
原题链接1221. 四平方和
题目难度：简单
题目来源：第七届蓝桥杯省赛C++ A/B组,第七届蓝桥杯省赛Java B/C组
题目描述四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
$5 = 0^2 + 0^2 + 1^2 + 2^2$$7 = 1^2 + 1^2 + 1^2 + 2^2$
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
$0 \le a \le b \le c \le d$
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入格式输入一个正整数 N。
输出格式输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围$0 < N < 5 * 10^6$
输入样例：15
输出样例：10 0 1 2
题目分析这道题的内容比较简洁，就是将一个整数分成四个整数的平方和的形式，有很多做法
我们可以大概分析一下，因为N是分成一个平方的，而$\...